Researches in the communication field such as mobile communication or deep space communication and in the broadcasting field such as digitalized terrestrial or satellite broadcasting have been recently advanced remarkably. Along with the advance, researches into coding theories have been also made vigorously for the purpose of increasing efficiency in error correction coding and decoding.
A so-called Shannon limit given by C. E. Shannon's theorem of communication channel coding has been known as a theoretical limit of code performance. The researches into coding theories have been made for the purpose of developing a code exhibiting performance close to the Shannon limit. As a coding method exhibiting performance close to the Shannon limit, there has been developed a method called Turbo coding such as parallel concatenated convolutional codes (PCCC) or serially concatenated convolutional codes (SCCC) in recent years. While these Turbo codes have been developed, low density parity check codes (hereinafter referred to as LDPC codes) have been moving into the limelight though the LDPC coding method is a coding method known from long ago.
The LDPC codes were initially proposed by R. G. Gallager in ‘R. G. Gallager, “Low Density Parity Check Codes”, Cambridge, Mass.: M.I.T. Press, 1963’, and then have come to be noticed again in ‘D. J. C. MacKay, “Good error correcting codes based on very sparse matrices”, Submitted to IEEE Trans. Inf. Theory, IT-45, pp. 399-431, 1999’, ‘M. G. Luby, M. Mitzenmacher, M. A. Shokrollahi and D. A. Spielman, “Analysis of low density codes and improved designs using irregular graphs”, in Proceedings of ACM Symposium on Theory of Computing, pp. 249-258, 1998’, etc.
According to the recent researches, it is being known that as the code length is increased, the LDPC codes can obtain performance close to the Shannon limit similarly to the Turbo codes or the like. In addition, since the LDPC codes have a trait that the minimum distance is proportional to the code length, the LDPC codes have a feature that block error probability characteristic is good, and an advantage that a so-called error floor phenomenon observed in decoding characteristic of the Turbo codes etc. hardly occurs.
Such an LDPC code will be hereinafter described specifically. Incidentally, the LDPC code is a linear code but not necessarily binary. Here, the LDPC code will be described as a binary code.
The LDPC code has the greatest feature in that a parity check matrix for defining the LDPC code is sparse. Here, the sparse matrix is constructed to have a very small number of components of “1” in the matrix. Assuming that the sparse parity check matrix is represented by H, then, for example, as shown in FIG. 1, there is a parity check matrix H in which the Hamming weight (the number of “1”) of each column is 3 and the Hamming weight of each row is 6.
An LDPC code defined by a parity check matrix H having a constant Hamming weight of each row and a constant Hamming weight of each column in this manner is referred to as a regular LDPC code. On the other hand, an LDPC code defined by a parity check matrix H having a non-constant Hamming weight of each row and a non-constant Hamming weight of each column is referred to as an irregular LDPC code.
Coding into such an LDPC code is achieved by a codeword which is generated in such a manner that a generator matrix G is generated based on a parity check matrix H and multiplied by a binary information message. Specifically, a coding device for performing coding into an LDPC code first calculates a generator matrix G which holds the equation GHT=0 with respect to a transposed matrix HT of the parity check matrix H. Here, the parity check matrix H is a matrix with (n-k) rows and n columns when the generator matrix G is a k×n matrix (a matrix with k rows and n columns).
The coding device generates a codeword (LDPC code) c (=uG) consisting of n bits by multiplying the generator matrix G by an information message (vector) u consisting of k bits.
The codeword c generated by the coding device is transmitted after mapped so that a bit with a value of “0” is changed to “+1” and a bit with a value of “1” is changed to “−1”. The transmitted codeword c is received on the receiver side through a predetermined communication channel.
For example, assuming a parity check matrix H consisting of (n-k) rows and n columns in the case where the codeword c consisting of n bits is a systematic code consistent with a bit string in which (n-k) parity bits are arranged following k bits of an information message u, and further assuming that an (n-k)-by-k matrix part corresponding to the k bits of the information message u in the n-bit codeword c is referred to as an information section and an (n-k)-by-(n-k) matrix part corresponding to the (n-k) parity bits in the n-bit codeword c is referred to as a parity section, then it is possible to code the information message u into an LDPC code using the parity check matrix H as long as the parity section is a lower or upper triangular matrix.
That is, for example, assuming that the parity check matrix H consists of an information section and a parity section of a lower triangular matrix as shown in FIG. 2, and further assuming that all components in the lower triangle of the parity section are “1”, then the first bit of the parity bits in the codeword c has a value obtained by EXORing (exclusive ORing) of bits of the information message u corresponding to components of “1” in the first row of the information section of the parity check matrix H.
In addition, the second bit of the parity bits in the codeword c has a value obtained by EXORing of bits of the information message u corresponding to components of “1” in the second row of the information section of the parity check matrix H and the first bit of the parity bits.
Further, the third bit of the parity bits in the codeword c has a value obtained by EXORing of bits of the information message u corresponding to components of “1” in the third row of the information section of the parity check matrix H and the first and second bits of the parity bits.
Hereinafter, in the same manner, the i-th bit of the parity bits in the codeword c has a value obtained by EXORing of bits of the information message u corresponding to components of “1” in the i-th row of the information section of the parity check matrix H and the first to (i-1)-th bits of the parity bits.
The (n-k) parity bits obtained in the aforementioned manner can be arranged following the k bits of the information message u to thereby obtain a codeword c consisting of n bits.
On the other hand, an LDPC code can be decoded by a message passing algorithm which is an algorithm called probabilistic decoding proposed by Gallager and which is based on belief propagation on a so-called Tanner graph having variable nodes (also called message nodes) and check nodes. Hereinafter, the variable nodes and the check nodes may be also generically referred to as nodes appropriately.
Messages exchanged between the nodes are real-valued in the probabilistic decoding. Therefore, it is necessary to trace a probability distribution of messages taking continuous values in order to find analytic solutions, so that analysis accompanied with very high difficulty is required. Accordingly, Gallager has proposed Algorithm A or Algorithm B as an algorithm for decoding an LDPC code.
Generally, an LDPC code is decoded in a procedure as shown in FIG. 3. Here, a reception value of an LDPC code (coded c) is regarded as U0, a message which may be hereinafter also referred to as check node message appropriately) outputted from a check node is regarded as uj, and a message (which may be hereinafter also referred to as variable node message appropriately) outputted from a variable node is regarded as vi. In addition, each message has a value of a real number expressing the likelihood of “C” in a so-called log likelihood ratio. The log likelihood ratio of the “0” likelihood of the reception value U0 is expressed as reception data u0i.
In decoding of an LDPC code, as shown in FIG. 3, in step S11, first, a reception value U0 (reception data u0i) is received, a message uj is initialized to “0”, and a variable k taking an integer as a counter for iterative processing is initialized to “0”. Then, the routine of processing goes to step S12. In the step S12, a variable node message vi is obtained by performing an operation represented by the expression (1) on the basis of the reception data u0i, and a check node message uj is obtained by performing an operation represented by the expression (2) on the basis of the variable node message vi.
                    [                  Numerical          ⁢                                          ⁢          Expression          ⁢                                          ⁢          1                ]                                                                      v          i                =                              u                          0              ⁢                                                          ⁢              i                                +                                    ∑                              j                =                1                                                              d                  c                                -                1                                      ⁢                          u              j                                                          (        1        )                                [                  Numerical          ⁢                                          ⁢          Expression          ⁢                                          ⁢          2                ]                                                                      tanh          ⁡                      (                                          u                j                            2                        )                          =                              ∏                          i              =              1                                                      d                c                            -              1                                ⁢                                          ⁢                      tanh            ⁡                          (                                                v                  i                                2                            )                                                          (        2        )            
Here, dv and dc in the expressions (1) and (2) are arbitrarily selectable parameters expressing the number of “1” in the longitudinal (row) direction of the parity check matrix H and the number of “1” in the horizontal (column) direction of the parity check matrix H, respectively. For example, in the case of a (3,6) code, dv=3 and dc=6.
Incidentally, in the operation represented by the expression (1) or (2), the range for the sum or product operation is 1 to dv−1 or 1 to dc−1 because a message inputted from a branch (edge) intended to output a message is not used as a parameter for the sum or product operation. Practically, the operation represented by the expression (2) can be performed by generating a table of a function R(v1, v2) defined by one output relative to two inputs v1 and v2 as shown in the expression (3) in advance and using this table continuously (recursively) as shown in the expression (4).[Numerical Expression 3]x=2 tan h−1{tan h(ν1/2)tan h(ν2/2)}=R(ν1,ν2)  (3)[Numerical Expression 4]uj=R(ν1,R(ν2,R(ν3, . . . R(νdc−2,νdc−1))))  (4)
In the step S12, the variable k is incremented by “1”. Then, the routine of processing goes to step S13. In the step S13, judgment is made as to whether or not the variable k is at least a predetermined iterative decoding number N. When the judgment in the step S13 makes a decision that the variable k is not at least N, the routine of processing goes back to the step S12. Then, the same processing is iterated.
When the judgment in the step S13 makes a decision that the variable k is at least N, the routine of processing goes to step S14 in which a message v is obtained by performing an operation represented by the expression (5) and outputted as an ultimately outputted decoding result. Then, the LDPC code decoding process is terminated.
                    [                  Numerical          ⁢                                          ⁢          Expression          ⁢                                          ⁢          5                ]                                                            v        =                              u                          0              ⁢                                                          ⁢              i                                +                                    ∑                              j                =                1                                            d                v                                      ⁢                          u              j                                                          (        5        )            
Here, differently from the operation represented by the expression (1), the operation represented by the expression (5) is performed by using messages given from all branches connected to a variable node.
In such decoding of an LDPC code, for example, in the case of a (3, 6) code, messages are exchanged between respective nodes as shown in FIG. 4. Incidentally, in FIG. 4, the operation represented by the expression (1) is performed in nodes (variable nodes) represented by “=” and the operation represented by the expression (2) is performed in nodes (check nodes) represented by “+”. Particularly in algorithm A, messages are binary-valued and EXORing of dc−1 messages inputted to a node represented by “+” is performed at the node whereas the inversion of the code is outputted at a node represented by “=” when dv−1 messages inputted to the node have all different bit values from reception data R(u0i).
On the other hand, researches into an implementation method for decoding an LDPC code have been also made in recent years. Decoding of an LDPC code will be modeled and described before description of the implementation method.
FIG. 5 shows an example of a parity check matrix for a (3, 6) LDPC code (of coding rate 1/2 and code length 12). The parity check matrix H for the LDPC code can be expressed in a Tanner graph as shown in FIG. 6. Here, in FIG. 6, a node represented by “+” is a check node and a node represented by “=” is a variable node. Each check node corresponds to a row in the parity check matrix H while each variable node corresponds to a column in the parity check matrix H. A line by which a check node and a variable node are connected is a branch (edge) and equivalent to “1” in the parity check matrix. That is, when a component located in the j-th row and the i-th column of the parity check matrix H is 1, the i-th variable node (“=” node) from top and the j-th check node (“+” node) from top are connected to each other by a branch in FIG. 6. Each branch indicates that a bit of the LDPC code corresponding to the variable node has a constraint condition corresponding to the check node. Incidentally, FIG. 6 is a Tanner graph showing the parity check matrix H in FIG. 5.
A sum production algorithm which is an LDPC code decoding method iterates the operation of a variable node and the operation of a check node.
The operation represented by the expression (1) is performed in a variable node as shown in FIG. 7. That is, in FIG. 7, a variable node message vi corresponding to a branch to be calculated is calculated using check node messages u1 and u2 from the other branches connected to the variable node, and reception data u0i. Variable node messages corresponding to the other branches are also calculated in the same manner respectively.
Before description of the operation of a check node, the expression (2) is rewritten as the expression (6) using the relation of the equation a×b=exp{ln(|a|)+ln(|b|)}×sign(a)×sign(b), in which the sign(x) expresses a sign (plus or minus) of x and takes 1 for x≧0 and −1 for x<0.
                    [                  Numerical          ⁢                                          ⁢          Expression          ⁢                                          ⁢          6                ]                                                                                                                u                j                            =                              2                ⁢                                                                  ⁢                                                      tanh                                          -                      1                                                        ⁡                                      (                                                                  ∏                                                  i                          =                          1                                                                                                      d                            c                                                    -                          1                                                                    ⁢                                                                                          ⁢                                              tanh                        ⁡                                                  (                                                                                    v                              i                                                        2                                                    )                                                                                      )                                                                                                                          =                              2                ⁢                                                                  ⁢                                                      tanh                                          -                      1                                                        ⁡                                      [                                          exp                      ⁢                                              {                                                                              ∑                                                          i                              =                              1                                                                                                                      d                                c                                                            -                              1                                                                                ⁢                                                      ln                            ⁡                                                          (                                                                                                                                tanh                                  ⁡                                                                      (                                                                                                                  v                                        i                                                                            2                                                                        )                                                                                                                                                              )                                                                                                      }                                            ×                                                                        ∏                                                      i                            =                            1                                                                                                              d                              c                                                        -                            1                                                                          ⁢                                                                                                  ⁢                                                  sign                          ⁡                                                      (                                                          tan                              ⁡                                                              (                                                                                                      v                                    i                                                                    2                                                                )                                                                                      )                                                                                                                ]                                                                                                                          =                              2                ⁢                                                                  ⁢                                                      tanh                                          -                      1                                                        ⁡                                      [                                          exp                      ⁢                                              {                                                  -                                                      (                                                                                          ∑                                                                  i                                  =                                  1                                                                                                                                      d                                    c                                                                    -                                  1                                                                                            ⁢                                                              -                                                                  ln                                  ⁡                                                                      (                                                                          tanh                                      ⁡                                                                              (                                                                                                                                                                                                                        v                                              i                                                                                                                                                                            2                                                                                )                                                                                                              )                                                                                                                                                        )                                                                          }                                                              ]                                                  ×                                                      ∏                                          i                      =                      1                                                                                      d                        c                                            -                      1                                                        ⁢                                                                          ⁢                                      sign                    ⁡                                          (                                              v                        i                                            )                                                                                                                              (        6        )            
Further assuming that a nonlinear function (nonlinear function) φ(x) is defined as the equation φ(x)=ln(tan h(x/2)) (in which ln( ) is a natural logarithm function) in x≧0, then the inverse function φ−1(x) of the nonlinear function φ(x) is expressed as the equation φ−1(x)=2 tan h−1(e−x). Accordingly, the expression (6) can be rewritten as the expression (7).
                    [                  Numerical          ⁢                                          ⁢          Expression          ⁢                                          ⁢          7                ]                                                                      u          j                =                                            ϕ                              -                1                                      ⁡                          (                                                ∑                                      i                    =                    1                                                                              d                      c                                        -                    1                                                  ⁢                                  ϕ                  ⁡                                      (                                                                                        v                        i                                                                                    )                                                              )                                ×                                    ∏                              i                =                1                                                              d                  c                                -                1                                      ⁢                                                  ⁢                          sign              ⁡                              (                                  v                  i                                )                                                                        (        7        )            
An operation represented by the expression (7) is performed in a check node as shown in FIG. 8. That is, in FIG. 8, a check node message uj corresponding to a branch to be calculated is calculated using variable messages v1, v2, v3, V4 and v5 from the other branches connected to the check node. Check node messages corresponding to the other branches are also calculated in the same manner respectively.
Incidentally, the function φ(x) can be also expressed as φ(x)=ln((ex+1)/ex−1)). In x>0, φ(x)=φ−1(x). When the functions φ(x) and φ−1(x) are implemented in apiece of hardware, LUT's (look up tables) may be used for the implementation. The LUT's are the same.
The method for decoding an LDPC code is also called belief propagation in addition to the sum product algorithm. In any case, the contents of operations to be performed are the same.
An implementation method in the case (of full serial decoding) where operations of nodes are performed one by one successively to thereby perform decoding will be described as an example of implementation of a sum product algorithm into a decoding device.
When the sum product algorithm is implemented in a piece of hardware, it is necessary to iteratively perform the variable node operation represented by the expression (1) and the check node operation represented by the expression (7) in a moderate circuit scale and with a moderate operating frequency.
Here, for example, assume that a code (of coding rate 2/3 and code length 108) represented by a parity check matrix H having 36 rows and 108 columns in FIG. 9 is decoded. The number of “1” in the parity check matrix H in FIG. 9 is 323. Accordingly, in a Tanner graph for the parity check matrix H, the number of branches is 323. Here, 0 is expressed as in the parity check matrix of FIG. 9.
FIG. 10 shows an example of configuration of a decoding device for decoding an LDPC code only in one cycle.
A message corresponding to one branch is calculated in accordance with each operating clock in the decoding device of FIG. 10.
That is, the decoding device in FIG. 10 includes two branch memories 100 and 102, one check node calculator 101, one variable node calculator 103, one receiving memory 104, and one control section 105.
In the decoding device of FIG. 10, messages are read one by one from the branch memory 100 or 102, so that the messages are used for calculating messages corresponding to desired branches. The messages obtained by the calculation are stored one by one in a post-stage branch memory 102 or 100. For performing decoding iteratively, decoding devices of FIG. 10 for performing deciding only in one cycle may be cascade-connected or a decoding device of FIG. 10 may be used iteratively to achieve iterative decoding. Here, for example, assume that a plurality of decoding devices of FIG. 10 are connected.
The branch memory 100 stores messages (variable node messages) D100 supplied from a variable node calculator 103 of an ante-stage decoding device (not shown), in the sequence where the messages D100 will be read by the post-stage check node calculator 101. In a phase of check node calculation, the branch memory 100 supplies the messages D100 as messages D101 to the check node calculator 101 in the sequence where the messages D100 were stored in the branch memory 100.
The check node calculator 101 performs an operation (check node operation) in accordance with the expression (7) by using the messages D101 (variable node messages vi) supplied from the branch memory 100 on the basis of a control signal D106 supplied from the control section 105, and supplies messages D102 (check node messages uj) obtained by the operation to the post-stage branch memory 102.
The branch memory 102 stores the messages D102 supplied from the ante-stage check node calculator 101 in the sequence where the messages D102 will be read by the post-stage variable node calculator 103. In a phase of variable node calculation, the branch memory 102 supplies the messages D102 as messages D103 to the variable node calculator 103 in the sequence where the messages D102 were stored in the branch memory 102.
While a control signal D107 is supplied from the control section 105 to the variable node calculator 103, reception data D104 are supplied from the receiving memory 104 to the variable node calculator 103. The variable node calculator 103 performs an operation (variable node operation) in accordance with the expression (1) by using the messages D103 (check node messages uj) supplied from the branch memory 100 and the reception data D104 (reception data u0i) supplied from the receiving memory 100 on the basis of the control signal D107, and supplies messages D105 (variable node messages vi) obtained as results of the operation to a branch memory 100 of a post-stage decoding device not shown.
The reception data u0i of the LDPC code are stored in the receiving memory 104. The control section 105 supplies the control signal D106 for controlling the variable node operation and the control signal D107 for controlling the check node operation, to the check node calculator 101 and the variable node calculator 103, respectively.
FIG. 11 shows an example of configuration of the check node calculator 101 of FIG. 10 for performing check node operations one by one.
In FIG. 11, the check node calculator 101 is shown on the assumption that each message is quantized into a total of 6 bits including a sign bit (bit for discriminating between plus and minus). That is, messages are expressed by 6-bit quantized values respectively and the 6-bit quantized values are assigned to numerical values which are obtained by equally dividing a predetermined numerical value range into 64 values which can be expressed by 6 bits including a sign bit.
In addition, a check node operation of the LDPC code expressed by the parity check matrix H of FIG. 9 is performed in FIG. 11. Further, a clock ck is supplied to the check node calculator 101 of FIG. 11. This clock ck is supplied to necessary blocks. Each block performs processing in synchronization with the clock ck.
The check node calculator 101 of FIG. 11 performs an operation in accordance with the expression (7) by using messages D101 (variable node messages vi) read one by one from the branch memory 100, for example, on the basis of a 1-bit control signal D106 supplied from the control section 105.
That is, in the check node calculator 101, the messages D101 (variable node messages vi) of 6 bits are read one by one from variable nodes corresponding to respective columns in the parity check matrix H, so that an absolute value D122 (|vi|) which is the lower 5 bits of each 6-bit message is supplied to a LUT 121 whereas a sign bit D121 which is the most significant bit of each 6-bit message is supplied to an EXOR circuit 129 and an FIFO (First In First Out) memory 133. In the check node calculator 101, a control signal D106 is given from the control section 105 and supplied to a selector 124 and a selector 131.
The LUT 121 reads a 5-bit operation result D123 (φ(|vi|)) as a result of the operation of the nonlinear function φ(|vi|) in the expression (7) on the absolute value D122 (|vi|) inputted therein, and supplies the 5-bit operation result D123 (φ(|vi|)) to an operation unit 122 and an FIFO memory 127.
The operation unit 122 integrates the operation result D123 by adding each operation result D123 (φ(|vi|)) to a 9-bit value D124 stored in a register 123, so that a 9-bit integrated value obtained as a result of the integration is stored in the register 123 again. Incidentally, when operation results D123 for absolute values D122 (|vi|) of messages D101 given from all branches corresponding to one row in the parity check matrix H have been integrated, the register 123 is reset.
Here, in the operation unit 122 and the register 123, the 5-bit operation result D123 (φ(|vi|)) supplied from the LUT 121 is integrated at maximum up to the maximum number of delay times in the FIFO memory 127, i.e. up to the number of times equal to the maximum weight of one row in the parity check matrix H. Now, the maximum weight of one row in the parity check matrix H in FIG. 9 is 9. Accordingly, in the operation unit 122 and the register 123, the 9-bit operation result D123 (φ(|vi|)) is integrated at maximum up to 9 times (nine 5-bit values are integrated). For this reason, at an output from the operation unit 122 and at outputs from portions after the operation unit 122, the number of quantization bits is 9 which is larger by 4 bits (the minimum number of bits capable of expressing 9 (times)) than the 5-bit operation result D1123 (φ(|vi|)) outputted by the LUT 121 so that a value obtained by integrating a 5-bit value 9 times can be expressed.
When messages D101 (variable node messages vi) corresponding to one row in the parity check matrix have been read one by one and an integrated value as a result of integration of operation results D123 corresponding to one row has been stored in the register 123, the control signal D106 supplied from the control section 105 changes from 0 to 1. When, for example, the row weight is “9”, the control signal D106 takes “0” for the first clock to the eighth clock and takes “1” for the ninth clock.
When the control signal D106 is “1”, the selector 124 selects a value stored in the register 123, i.e. a 9-bit value D124 (Σφ(|vi|) from i=1 to i=dc) as a result of integration of φ(|vi|) calculated from messages D101 (variable node messages vi) given from all branches corresponding to one row in the parity check matrix H, and outputs the 9-bit value D124 as a value D125 so that the value D125 is stored in a register 125. The register 125 supplies the stored value D125 as a 9-bit value D126 to the selector 124 and an operation unit 126. When the control signal D106 is “0”, the selector 124 selects a value D126 supplied from the register 125, and outputs the value D126 so that the value D126 is stored in the register 125 again. That is, the register 125 supplies φ(|vi|) integrated at the last time, to the selector 124 and the operation unit 126 unless φ(|vi|) calculated from messages D101 (variable node messages vi) given from all branches corresponding to one row in the parity check matrix H are integrated completely.
On the other hand, the FIFO memory 127 delays the 5-bit operation result D123 (φ(|vi|)) outputted by the LUT 121 until a new value D126 (Σφ(|vi|) from i=1 to i=dc) is outputted from the register 125, and supplies the 5-bit operation result D123 (φ(|vi|)) as a 5-bit value D127 to the operation unit 126. The operation unit 126 subtracts the value D127 supplied from the FIFO memory 127, from the value D126 supplied from the register 125, and supplies a result of the subtraction as a 5-bit difference value D128 to an LUT 128. That is, the operation unit 126 subtracts φ(|vi|) calculated from a message D101 (variable node message vi) given from a branch intended to calculate the check node message uj, from the integrated value of φ(|vi|) obtained from messages D101 (variable node messages vi) given from all branches corresponding to one row in the parity check matrix H, and supplies the difference value (Σφ(|vi|) from i=1 to i=dc−1) as a difference value D128 to an LUT 128.
Incidentally, since the operation unit 126 subtracts the 5-bit value D127 supplied from the FIFO memory 127, from the 9-bit value D126 supplied from the register 125, a result of the subtraction may be 9 bits at maximum. However, the operation unit 126 outputs a 5-bit difference value D128. For this reason, when a subtraction result as a result of subtraction of a 5-bit value D127 supplied from the FIFO memory 127 from a 9-bit value D126 supplied from the register 125 cannot be expressed by 5 bits, that is, when a subtraction result exceeds the maximum value (31 (11111 in binary)) which can be expressed by 5 bits, the operation unit 126 clips the subtraction result to the maximum value which can be expressed by 5 bits, and outputs the clipped value as a 5-bit difference value D128.
The LUT 128 outputs a 5-bit operation result D129 (φ−1(Σφ(|vi|))) as a result of the operation of the inverse function φ−1(Σφ(|vi|)) in the expression (7) on the difference value D128 (Σφ(|vi|) from i=1 to i=dc−1).
In parallel with the aforementioned processing, the EXOR circuit 129 performs EXORing of a 1-bit value D131 stored in the register 130 and a sign bit D121 to thereby multiply the sign bits by each other, and stores a thus obtained 1-bit multiplication result D130 in the register 130 again. Incidentally, when sign bits D121 of messages D101 (variable node messages vi) given from all branches corresponding to one row in the parity check matrix H have been multiplied completely, the register 130 is reset.
When a multiplication result D130 (Πsign(vi) from i=1 to dc) as a result of multiplication of sign bits D121 of messages D101 given from all branches corresponding to one row in the parity check matrix H has been stored in the register 130, the control signal D106 supplied from the control section 105 changes from “0” to “1”.
When the control signal D106 is “1”, the selector 131 selects a value stored in the register 130, that is, a value D131 (Πsign (vi) from i=1 to i=dc) as a result of multiplication of sign bits D121 of messages D101 given from all branches corresponding to one row in the parity check matrix H, and outputs the value D131 as a 1-bit value D132 so that the 1-bit value D132 is stored in a register 132. The register 132 supplies the stored value D132 as a 1-bit value D133 to the selector 131 and an EXOR circuit 134. When the control signal D106 is “0”, the selector 131 selects a value D133 supplied from the register 132, and outputs the value D133 so that the value D133 is stored in the register 132 again. That is, the register 132 supplies a value stored at the last time, to the selector 131 and the EXOR circuit 134 unless sign bits D121 of messages D101 (variable node messages vi) given from all branches corresponding to one row in the parity check matrix H are multiplied completely.
On the other hand, the FIFO memory 133 delays the sign bit D121 until a new value D133 (Πsign(vi) from i=1 to i=dc) is supplied from the register 132 to the EXOR circuit 134, and supplies the sign bit D121 as a 1-bit value D134 to the EXOR circuit 134. The EXOR circuit 134 performs EXORing of the value D133 supplied from the register 132 and the value D134 supplied from the FIFO memory 133 to thereby divide the value D133 by the value D134 and output a 1-bit division result as a quotient value D135. That is, the EXOR circuit 134 divides the product value of sign bits D121 (sign(|vi|)) of messages D101 given from all branches corresponding to one row in the parity check matrix H by a sign bit D121 (sign(|vi|)) of a message D101 given from a branch intended to calculate the check node message uj, and outputs a quotient value (Πsign(vi) from i=1 to i=dc−1) as a quotient value D135.
A total of 6 bits including the 5-bit operation result D129 outputted from the LUT 128 as the lower 5 bits of the 6 bits, and the 1-bit quotient value D135 outputted from the EXOR circuit 134 as the most significant bit (sign bit) of the 6 bits are outputted as a message D102 (check node message uj) from the check node calculator 101.
As described above, the operation represented by the expression (7) is performed by the check node calculator 101 so that a check node message uj is obtained.
Since the maximum weight of one row in the parity check matrix H in FIG. 9 is 9, that is, since the maximum number of variable node messages vi supplied to a check node is 9, the check node calculator 101 has the FIFO memory 127 and the FIFO memory 133 for delaying nonlinear function operation results (φ(|vi|)) of 9 check node messages vi. To calculate a check node message uj in a row whose row weight is smaller than 9, the delay amount in the FIFO memory 127 and the FIFO memory 133 is reduced to a value equal to the row weight.
FIG. 12 shows an example of configuration of the variable node calculator 103 of FIG. 10 for performing variable node operations one by one.
Similarly to FIG. 11, FIG. 12 also shows a variable node calculator 103 on the assumption that each message is quantized into a total of 6 bits including a sign bit.
Further, also in FIG. 12, a variable node operation of an LDPC code expressed by the parity check matrix H of FIG. 9 is performed. A clock ck is supplied to the variable node calculator 103 of FIG. 12. This clock ck is supplied to necessary blocks. Each block performs processing in synchronization with the clock ck.
The variable node calculator 103 of FIG. 12 performs an operation (variable node operation) in accordance with the expression (1) by using messages D103 read one by one from the branch memory 102 and reception data D104 (u0i) read from the receiving memory 104, for example, on the basis of a 1-bit control signal D107 supplied from the control section 105.
That is, in the variable node calculator 103, 6-bit messages D103 (check node messages uj) given from check nodes corresponding to each row in the parity check matrix H are read one by one and supplied to an operation unit 151 and an FIFO memory 155. Also in the variable node calculator 103, 6-bit receiving data D104 (u0i) are read one by one from the receiving memory 104 and supplied to an operation unit 156. Further, a control signal D107 given from the control section 105 is supplied to the variable node calculator 103 so that the control signal D107 is supplied to a selector 153.
The operation unit 151 integrates a 6-bit message D103 (check node message uj) by adding the 6-bit message D103 to a 9-bit value D151 stored in a register 152, and stores a 9-bit integrated value obtained as a result of the integration in the register 152 again. Incidentally, when messages D103 given from all branches corresponding to one column in the parity check matrix H have been integrated completely, the register 152 is reset.
Here, in the operation unit 151 and the register 152, the 6-bit message D103 is integrated at maximum up to the maximum number of delay times in the FIFO memory 155, i.e. the number of times equal to the maximum weight of one column in the parity check matrix H. Now, the maximum weight of one column in the parity check matrix H in FIG. 9 is 5. Accordingly, in the operation unit 151 and the register 152, the 6-bit message D103 is integrated at maximum up to 5 times (five 6-bit values are integrated). For this reason, at an output from the operation unit 151 and at outputs from portions after the operation unit 151, the number of quantization bits is 9 which is larger by 3 (the minimum number of bits capable of expressing 5 (times)) than the 6-bit message D103 so that a value obtained by integration of a 6-bit value 5 times can be expressed.
When messages D103 corresponding to one column in the parity check matrix H have been read one by one and an integrated value of the messages D103 corresponding to one column has been stored in the register 152, the control signal D107 supplied from the control section 105 changes from “0” to “1”. When, for example, the column weight is “5”, the control signal D107 takes “0” for the first clock to the fourth clock and takes “1” for the fifth clock.
When the control signal D107 is “1”, the selector 153 selects a value stored in the register 152, i.e. a 9-bit value D151 (Σuj from j=1 to dv) as a result of integration of messages D103 (check node messages uj) given from all branches corresponding to one column in the parity check matrix H, and outputs the 9-bit value D151 so that the 9-bit value D151 is stored in a register 154. The register 154 supplies the stored value D151 as a 9-bit value D152 to the selector 153 and the operation unit 156. When the control signal D107 is “0”, the selector 153 selects a value D152 supplied from the register 154, and outputs the value D152 so that the value D152 is stored in the register 154 again. That is, the register 154 supplies a value integrated at the last time, to the selector 153 and the operation unit 156 unless messages D103 (check node messages uj) given from all branches corresponding to one column in the parity check matrix H are integrated completely.
On the other hand, the FIFO memory 155 delays a message D103 given from a check node until a new value D152 (Σuj from j=1 to j=dv) is outputted from the register 154, and supplies the message D103 as a 6-bit value D153 to the operation unit 156. The operation unit 156 subtracts the value D153 supplied from the FIFO memory 155, from the value D152 supplied from the register 154. That is, the operation unit 156 subtracts a check node message uj given from a branch intended to calculate a variable node message vi, from the integrated value of messages D103 (check node messages uj) given from all branches corresponding to one column in the parity check matrix H to thereby obtain a difference value (Σuj from j=1 to j=dv−1). Further, in the operation unit 156, reception data D104 (u0i) supplied from the receiving memory 104 are added to the difference value (Σuj from j=1 to j=dv−1), so that a 6-bit value obtained as a result of the addition is outputted as a message D105 (variable node message vi).
As described above, the operation represented by the expression (1) is performed by the variable node calculator to thereby obtain a variable node message vi.
Incidentally, since the maximum weight of one column in the parity check matrix H in FIG. 9 is 5, that is, since the maximum number of check node messages uj supplied to a variable node is 5, the variable node calculator 103 has the FIFO memory for delaying five check node messages uj. To calculate a variable node message vi for a column whose column weight is smaller than 5, the delay amount in the FIFO memory 155 is reduced to a value equal to the column weight.
In addition, the operation unit 156 performs an operation of subtracting the 6-bit value D153 supplied from the FIFO memory 155 from the 9-bit value D152 supplied from the register 154 and of adding the 6-bit reception data D104 supplied from the receiving memory 104, so that a result of the operation may be smaller than the minimum value which can be expressed by a 6-bit message D105 or may be larger than the maximum value which can be expressed by the 6-bit message D105. When the operation result is smaller than the minimum value which can be expressed by the 6-bit message D105, the operation unit 156 clips the operation result to the minimum value. When the operation result is larger than the maximum value which can be expressed by the 6-bit message D105, the operation unit 156 clips the operation result to the maximum value.
In the decoding device of FIG. 10, control signals are given from the control section 105 in accordance with the weight of the parity check matrix H. According to the decoding device of FIG. 10, the control signals can be changed simply to make it possible to decode a variety of LDPC codes of parity check matrices H as long as capacities of the branch memories 100 and 102 and the FIFO memories 127, 133 and 155 of the check node calculator 101 and the variable node calculator 103 are sufficient.
Although not shown, in an ultimate stage of decoding in the decoding device of FIG. 10, an operation represented by the expression (5) is performed in place of the variable node operation represented by the expression (1), so that a result of the operation is outputted as an ultimate decoding result.
When the decoding device of FIG. 10 is used iteratively for decoding an LDPC code, the check node operation and the variable node operation are performed alternately. That is, in the decoding device of FIG. 10, the variable node calculator 103 performs the variable node operation by using results of the check node operation performed by the check node calculator 101 whereas the check node calculator 101 performs the check node operation by using results of the variable node operation performed by the variable node calculator 103.
Incidentally, although the decoding device of FIG. 10 is a full serial decoding device for decoding an LDPC code by performing operations of respective nodes one by one successively, other devices such as a full parallel decoding device (e.g. see Non-Patent Document 1) for performing operations of all nodes simultaneously, and a partly parallel decoding device (e.g. see Non-Patent Document 2 and Patent Document 1) for performing operations of neither one node nor all nodes but a certain number of nodes simultaneously have been also proposed.
For example, in the decoding device of FIG. 10, at least a bit number equal to a product of the code length of an LDPC code and the bit number (the number of quantization bits) of a quantized value for expressing reception data D104 is required as storage capacity of the receiving memory 104 for storing reception data D104. Moreover, at least a bit number equal to a product of the total number of branches (total branch number) and the bit number (the number of quantization bits) of a quantized value for expressing a message is required as storage capacity of the branch memory 100 or 102 for storing messages.
Accordingly, when the code length is 108, the bit number of a quantized value for expressing a message (including reception data D104) is 6, and the number of branches is 323 as described above, a receiving memory 104 having storage capacity of at least 648 (=108×6) bits, and branch memories 100 and 102 each having storage capacity of at least 1938 (=323×6) bits are required.
Although here is shown the case where the code length is 108 for the sake of simplification of description, a value of about several thousands can be practically used as the code length of an LDPC code.
On the other hand, in order to improve accuracy in decoding of an LDPC code, it is simply necessary to use a quantized value having a number of bits to a certain degree, as a quantized value for expressing a message including reception data D104.
As described above, storage capacities of the branch memories 100 and 102 and the receiving memory 104 are however proportional to the bit number of a quantized value for expressing a message. Accordingly, when a message is expressed by a quantized value with a large bit number, a large capacity memory is required as a memory serving as a constituent portion of the decoding device, to thereby result in an increase of the scale of the device.    Patent Document 1: JP-A-2004-364233    Non-Patent Document 1: C. Howland and A. Blanksby, “Parallel Decoding Architectures for Low Density Parity Check Codes”, Symposium on Circuits and Systems, 2001    Non-Patent Document 2: E. Yeo, P. Pakzad, B. Nikolic and V. Anantharam, “VLSI Architectures for iterative Decoders in Magnetic Recording Channels”, IEEE Transactions on Magnetics, Vol. 37, No. 2, March 2001